package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 抄的答案，这题没思路
 *
 * 答案思路为：记录每个heights数字中以 heights[i] 画出矩形的左右边界
 *
 * @author qidi
 * @date 2021-12-21 15:16:42
 */
class Q0084_LargestRectangleInHistogram {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int length = heights.length;
            int[] left = new int[length];
            int[] right = new int[length];
            Arrays.fill(right, length);

            Deque<Integer> deque = new ArrayDeque<>();

            for (int i = 0; i < length; i++) {
                while (!deque.isEmpty() && heights[deque.peek()] >= heights[i]) {
                    Integer r = deque.pop();
                    right[r] = i;
                }
                left[i] = deque.isEmpty() ? -1 : deque.peek();
                deque.push(i);
            }

            int maxArea = 0;

            for (int i = 0; i < length; i++) {
                maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
            }

            return maxArea;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0084_LargestRectangleInHistogram().new Solution();
        System.out.println(solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(solution.largestRectangleArea(new int[]{2, 4}));
    }
}